/******************************************************************************
 * $Id: sort.h,v 1.4 2004/09/22 01:14:28 jimb Exp $
 * @file
 * @author  Jim Brooks http://www.jimbrooks.org
 ******************************************************************************/

#ifndef SORT_H
#define SORT_H

/* --- inline --- */

extern inline void
GlistInsert( GList* pLinkPreceding,
             GList* pLinkToInsert );

extern inline void
GlistPrepend( GList* pGlist,
              GList* pLinkToPrepend );

extern inline void
GlistRemoveNonFirstLink( GList* pGlist,
                         GList* pLinkToRemove );

/* -------------- */

GList*
InsertionSortGlist( GList* pGlist );

/*****************************************************************************
 * Insert a link into a GList.
 * @param   pLinkPreceding
 *          The link in the GList preceding the link to be inserted.
 * @param   pLinkToInsert
 *          The link to insert.
 *****************************************************************************/
extern inline void
GlistInsert( GList* pLinkPreceding,
             GList* pLinkToInsert )
{
#ifndef HYPERSRC_SPEED
   g_assert( pLinkPreceding && pLinkToInsert );
#endif

  /*
   * Is the preceding link the last?
   */
   if ( pLinkPreceding->next )
   {
     /*
      * The preceding link is in the middle somewhere.
      */
      GList* pLinkThird = pLinkPreceding->next;

     /*
      * Update preceding link.
      */
      pLinkPreceding->next = pLinkToInsert;

     /*
      * Update link to insert.
      */
      pLinkToInsert->prev = pLinkPreceding;
      pLinkToInsert->next = pLinkThird;

     /*
      * Update link that is after the inserted link.
      */
      pLinkThird->prev = pLinkToInsert;
   }
   else
   {
     /*
      * The preceding link is last.
      * Therefore, the operation requires is actually an append.
      */
      pLinkPreceding->next = pLinkToInsert;

      pLinkToInsert->prev = pLinkPreceding;
      pLinkToInsert->next = NULL;
   }
}

/*****************************************************************************
 * Prepend a link into a GList.
 * @param   pGlist
 * @param   pLinkToPrepend.
 *          The link to insert.
 *****************************************************************************/
extern inline void
GlistPrepend( GList* pGlist,
              GList* pLinkToPrepend )
{
#ifndef HYPERSRC_SPEED
   g_assert( pGlist && pLinkToPrepend );
#endif

   pGlist->prev = pLinkToPrepend;

   pLinkToPrepend->prev = NULL;
   pLinkToPrepend->next = pGlist;
}

/*****************************************************************************
 * This sleezy function is optimized to remove a non-first link.
 *****************************************************************************/
extern inline void
GlistRemoveNonFirstLink( GList* pGlist,
                         GList* pLinkToRemove )
{
  /*
   * Assumption is that there is a preceding link.
   */
   pLinkToRemove->prev->next = pLinkToRemove->next;

  /*
   * There might[not] be a successor.
   */
   if (pLinkToRemove->next)
      pLinkToRemove->next->prev = pLinkToRemove->prev;

  /*
   * For speed, skip nullifying the next/prev in the removed link.
   */
#if 0
   pLinkToRemove->next = NULL;
   pLinkToRemove->prev = NULL;
#endif
}

#endif /* SORT_H */
